package com.wangbo.basic;

import lombok.experimental.UtilityClass;

/**
 * 递归工具类
 */
@UtilityClass
public class RecursionUtil {
    /**
     * 阶乘求积
     */
    public int factorial(int n) {
        // 基本情形
        if (n == 0 || n == 1) {
            return 1;
        }
        // 递归情形
        return n * factorial(n - 1);
    }

    /**
     * 数组有序:
     * 判断数组从指定位置开始往后，是否一直递增(包括等值)
     */
    public boolean isArrayIncreased(int[] arr, int begin) {
        // 基本情形: begin是数组末尾
        if (begin == arr.length - 1) {
            return true;
        }
        // 基本情形
        if (arr[begin] > arr[begin + 1]) {
            return false;
        }

        // 递归情形
        return isArrayIncreased(arr, begin + 1);
    }

    /**
     * 上楼梯：
     * 每次走1或2或3阶台阶，上n阶楼梯,有多少种不同走法
     */
    public int goUpstairs(int n) {
        // 基本情形
        if (n == 1) {
            return 1;
        }
        // 基本情形
        if (n == 2) {
            return 2;
        }
        // 基本情形
        if (n == 3) {
            return 4;
        }

        // 递归情形
        return goUpstairs(n - 1) + goUpstairs(n - 2) + goUpstairs(n - 3);
    }
}
